In color image processing it is often required to transform color image signals from one color space such as R,G,B to another such as C,M,Y,K. This transformation is frequently performed by employing three or four dimensional lookup tables to transform electronic image data representing color images from one color space to another, and also to transform color data from an input device into a desired color representation for an output device. These tables consist of sparsely spaced data points regularly populating the three or four dimensional input color space and the output data is derived generally by performing a linear interpolation or signal dependent matrix operations on neighboring values over regularly defined regions within the input space. See for example U.S. Pat. No. 4,275,413, entitled "Linear Interpolation for Color Correction," issued Jun. 23, 1981 to Sakamoto, et al.; U.S. Pat. No. 4,511,989, "Linear Interpolating Method and Color Conversion Apparatus Using This Method," issued Apr. 16, 1985 to Sakamoto; and U.S. Pat. No. 4,346,402 "Image Reproduction Apparatus": issued Aug. 24, 1982 to Pugsley. Generally speaking, these regions in the input color space are defined by a list of points within a lookup table arranged in a manner to facilitate retrieval. As shown in FIG. 2, these points are samples on a three or four dimensional grid. FIG. 2 shows an example of the division of a three dimensional volume where the coordinate axis are labeled A, B and C and may represent for example R, G, B color components. This construction is, however, non-optimal because when a linear or matrix approximation technique is used for interpolation, error is introduced by the straight line approximation of the interpolation technique. The magnitude of the error is related to the local curvature on a slope of the transformation function. This error can become extreme near a color gamut boundary, in certain regions of the color space depending on the specific color transformation.
To illustrate the problem, a function f(x) is shown in FIG. 4, having a high rate of curvature between the samples at n and n+1. The interpolated value f(x) between n and n+1 contains a large error, whereas the interpolated values f(x.sub.o) and f(x.sub.2) do not.
FIG. 3 is a schematic diagram illustrating this prior art technique for performing transformations on data. As shown in FIG. 3, lookup table 10 contains a regular sample of transformed data values f(x), The lookup table 10 and associated control logic is arranged to output a plurality of neighboring transformed values f(n) and f(n+1) where x is between n and n+1, in response to the high order bits of an input data value x. The transformed values f(n) and f(n+1) are supplied to an interpolator 12, along with the low order bits of the input data value. The interpolator 12 employs the low order bits as an interpolation factor F to interpolate a value f(x) between f(n) and f(n+1). Although the example in FIG. 3 is shown as a one dimensional interpolator for ease of description, the concept is readily extended to higher dimensions such as three dimensions for color image signals.
In an attempt to further reduce the size of the lookup table 10, for multidimensional data, such as color image data, it is known to perform a further transformation on each color component of the input image data prior to performing the color transformation to reduce the number of bits in the component data values. See U.S. Pat. No. 4,346,402 issued Aug. 24, 1982 to P. C. Pugsley. Also, for color image signals, special three dimensional interpolation algorithms have been proposed for increasing the efficiency of the interpolator 12. See for example U.S. Pat. No. 4,275,413 issued to Sakamoto et al., Jun. 23, 1981; U.S. Pat. No. 4,477,833 issued Oct. 16, 1984 to Clark et al,; and U.S. Pat. No. 4,511,989 issued Apr. 16, 1985 to Sakamoto.
All of these prior art approaches suffer from the shortcoming that in regions where the multi-dimensional transformation function exhibits a high curvature, the interpolation results in greater error. If this problem is remedied simply by sampling the output values at a higher frequency to reduce the error, the size of the lookup table memory holding the sample of output values is greatly increased, and therefore becomes prohibitively costly.